/*
#Copyright (c) 2013, Philippe Bordron <philippe.bordron@gmail.com>
#
# This file is part of SIPPER.
#
# DCC is free software: you can redistribute it and/or modify
# it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# DCC is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU LESSER GENERAL PUBLIC LICENSE for more details.
#
# You should have received a copy of the GNU LESSER GENERAL PUBLIC LICENSE
# along with SIPPER.  If not, see <http://www.gnu.org/licenses/>
*/
package combi.wip.sipper.modules;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;
import java.util.Map.Entry;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import combi.wip.sipper.modeling.metabolicNetwork.graphs.ReactionGraph;
import combi.wip.sipper.modeling.metabolicNetworks.ImplOfFilteredMetabolicNetwork;
import combi.wip.sipper.modeling.metabolicNetworks.MetabolicNetwork;
import combi.wip.sipper.modeling.metabolicNetworks.MetabolicNetworkUtils;
import combi.wip.sipper.modeling.reactions.Reaction;

import org.jgrapht.DirectedGraph;
import org.jgrapht.GraphPath;
import org.jgrapht.alg.DijkstraShortestPath;
import org.jgrapht.ext.DOTExporter;
import org.jgrapht.ext.IntegerNameProvider;
import org.jgrapht.ext.StringNameProvider;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DefaultWeightedEdge;

import combi.wip.sipper.io.IOMetabolicNetwork;
import combi.wip.sipper.io.dot.DOTColorSubgraphExporter;
import combi.wip.sipper.io.dot.DOTColorWithFullSubgraphExporter;
import combi.wip.sipper.io.dot.DOTWeightedEdgeNameProvider;
import combi.wip.sipper.io.metacyc.IOMetabolicNetworkFromMetaCyc;

import combi.utils.Couple;
import combi.utils.Triplet;

public class GroupeFeuilles2 {

	private static String extTemplateGraph = ".dot";

	public static void main(String[] args) throws IOException {
		/*
		 * Calcul des modules a partir des chemins feuilles (non inclus dans d'autres)
		 */

		String fileLeaves = args[0];
		String repOut = args[1];
		String fileReactions = args[2];	
		String fileComposants = args[3];	
		int metaboliteCutOff=Integer.parseInt(args[4]);


		String pathTemplateGraph = repOut+ "/mod_";

		// charge feuilles Treillis
		Couple<Collection<List<List<Couple<String, String>>>>, Map<List<Couple<String, String>>, Couple<Double,Integer>>> feuilles = null;
		try{
			System.err.println("Chargement des feuilles");
			feuilles = chargeFeuilles(fileLeaves);
			System.err.println(feuilles.getFirst().size() + " feuilles");
			/*for (List<Couple<String, String>> f : feuilles)
				System.err.println(f);*/
		}
		catch(Exception e)
		{
			e.printStackTrace();
			System.exit(1);
		}

		// fusionne les chemins avec sommets communs pour obtenir sous-graphes.
		System.err.println("Creation des clusters de feuilles");
		Map<List<List<Couple<String, String>>>, Set<List<List<Couple<String, String>>>>> assoFeuilles = new HashMap<List<List<Couple<String, String>>>, Set<List<List<Couple<String, String>>>>>();
		for (List<List<Couple<String, String>>> ch : feuilles.getFirst())
		{
			Set<List<List<Couple<String, String>>>> identite  = new HashSet<List<List<Couple<String, String>>>>();
			identite.add(ch);
			assoFeuilles.put(ch,identite);
		}
		//System.err.println(assoFeuilles);


		for (List<List<Couple<String, String>>> ch1 : feuilles.getFirst())
		{
			for (List<List<Couple<String, String>>> ch2 : feuilles.getFirst())
			{
				if (!ch1.equals(ch2))
				{
					Set<Couple<String,String>> commun = new HashSet<Couple<String,String>>();
					for (List<Couple<String,String>> p1 : ch1)
					{
						commun.addAll(p1);
					}

					Set<Couple<String,String>> retain = new HashSet<Couple<String,String>>();
					for (List<Couple<String,String>> p2 : ch2)
					{
						retain.addAll(p2);
					}

					commun.retainAll(retain);
					if (!commun.isEmpty())
					{
						//System.err.println("\t" + ch1 + "\n\t"+ ch2);
						Set<List<List<Couple<String, String>>>> temp1 = assoFeuilles.get(ch1);
						Set<List<List<Couple<String, String>>>> temp2 = assoFeuilles.get(ch2);
						temp1.addAll(temp2);
						for (List<List<Couple<String, String>>> ch : temp2)
						{
							assoFeuilles.put(ch, temp1);
						}
						//temp2.clear();
					}
					retain.clear();
				}
			}
		}		
		//generation des sous-graphes
		Collection<Set<List<List<Couple<String, String>>>>> clustersDeChemins = new HashSet<Set<List<List<Couple<String, String>>>>>(assoFeuilles.values());
		System.err.println(clustersDeChemins.size() + " clusters de chemins");
		//System.err.print(assoFeuilles);

		System.err.println("Export des " + clustersDeChemins.size() + " modules");
		int cpt = 0;
		File f = new File(pathTemplateGraph+ ".txt");
		// tester si le parent (qui est un répertoire existe)
		File p = f.getParentFile(); // me souvient plus de la méthode
		if (!p.exists())
		{
			p.mkdirs(); // créer le rep
		}
		else
		{
			for (File temp : p.listFiles())
			{
				//System.err.println(temp);
				temp.delete();
			}
		}
		try{
			BufferedWriter out = new BufferedWriter(new FileWriter(f));
			for(Set<List<List<Couple<String, String>>>> kchemins : clustersDeChemins)
			{
				cpt++;
				out.write("mod_"+cpt+ "\n");
				for (List<List<Couple<String, String>>> kSIP : kchemins)
				{
					for (List<Couple<String, String>> path : kSIP)
					{
						out.write(feuilles.getSecond().get(path).getFirst()+"\t" + feuilles.getSecond().get(path).getSecond() + "\t" + path.toString().replaceAll("\\[\\]", "")+"\n");
					}
				}
				out.write("\n");
			}
			out.close();
		}
		catch(IOException e)
		{
			// TODO Auto-generated catch block
			e.printStackTrace();		
		}

		Collection<DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>> graphes = new ArrayList<DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>>(clustersDeChemins.size());

		System.err.println("Generation des sous-graphes des modules");
		for(Set<List<List<Couple<String, String>>>> kchemins : clustersDeChemins)
		{
			DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge> graph = new DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>(DefaultWeightedEdge.class);
			for (List<List<Couple<String, String>>> chemins : kchemins)
			{
				for (List<Couple<String, String>> ch : chemins)
				{
					Couple<String, String> v1 = null;
					for (Couple<String, String> v2 : ch)
					{
						if(! graph.containsVertex(v2))
						{
							graph.addVertex(v2);
						}
						if (v1 != null && !graph.containsEdge(v1, v2))
						{
							graph.addEdge(v1, v2);
							//graph.setEdgeWeight(graph.getEdge(v1, v2), poids);
						}
						v1 = v2; 
					}
				}
				chemins.clear();
			}
			graphes.add(graph);
			kchemins.clear();
		}

		clustersDeChemins.clear();
		// export des sous-graphes

		System.err.println("Export des " + graphes.size() + " sous-graphes");
		cpt = 0;
		f = new File(pathTemplateGraph + cpt + extTemplateGraph);
		// tester si le parent (qui est un répertoire existe)
		p = f.getParentFile(); // me souvient plus de la méthode
		for (DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge> graph : graphes)
		{
			cpt++ ;
			DOTExporter<Couple<String,String>, DefaultWeightedEdge> outModele = new DOTExporter<Couple<String,String>, DefaultWeightedEdge>(new IntegerNameProvider<Couple<String,String>>(), new StringNameProvider<Couple<String,String>>(),null);
			try {

				outModele.export(new BufferedWriter(new FileWriter(pathTemplateGraph + cpt + extTemplateGraph)), graph);
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}

		/*
		 *  liens orientés entres les sous-graphes (plus court chemin en nombre de reactions entre 2 sommets distincts des sous-graphes).
		 */

		// recuperation des sommets de chaque sous-graphes.
		Collection<Set<Couple<String, String>>> classesSommets = new ArrayList<Set<Couple<String, String>>>(graphes.size());
		Collection<Set< String>> classesReactions = new ArrayList<Set<String>>(graphes.size());
		Map<String, Set<DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>>> reactionsCommunes = new HashMap<String, Set<DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>>>();
		for (DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge> graph : graphes)
		{
			Set<Couple<String,String>> sommets = graph.vertexSet();
			Set<String> reactions = new HashSet<String>();
			for (Couple<String,String> s : sommets)
			{
				reactions.add(s.getSecond());
				//reactions communes
				Set<DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>> temp = reactionsCommunes.get(s.getSecond());
				if (temp == null)
				{
					temp = new HashSet<DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>>();
					reactionsCommunes.put(s.getSecond(), temp);
				}
				temp.add(graph);
			}
			classesSommets.add(sommets);
			classesReactions.add(reactions);			
		}
		//TODO detection des reactions communes a des graphes

		// chargement du metabolisme : cf CreationModeleEcocyc

		IOMetabolicNetwork<String, Reaction<String>> metaIO = new IOMetabolicNetworkFromMetaCyc(fileComposants, fileReactions);
		metaIO.load();
		MetabolicNetworkUtils<String, Reaction<String>> metaUtil = new MetabolicNetworkUtils<String, Reaction<String>>();
		Map<String, Integer> cutMap = metaUtil.compoundsCount(metaIO.get());
		Collection<String> cutSet = new HashSet<String>();
		for (Entry<String, Integer> entry : cutMap.entrySet())
		{
			if (entry.getValue()>metaboliteCutOff)
			{
				cutSet.add(entry.getKey());
			}
		}
		MetabolicNetwork<String, Reaction<String>> meta = new ImplOfFilteredMetabolicNetwork<String, Reaction<String>>(metaIO.get(),cutSet);
		//meta.charge(fileComposants, fileReactions, fileEnzymeReactions, fileProteines, fileClasses);

		ReactionGraph<String, Reaction<String>> graphReactionsCreator = new ReactionGraph<String, Reaction<String>>(meta);
		DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> graphReactions = toWeigthedGraph(graphReactionsCreator.generateGraph());
		//System.err.println(graphReactions.vertexSet());

		// modification du metabolisme pour prise en compte des sous-graphes :
		// remplacement des noeuds correspondant a chaque sous-graphe par un unique noeud (contraction).
		// si deux sous-graphes distincts se partagent une reaction (mais pas le même sommet necessairement), il y aura 2 noeuds distincts.
		Map<String, String> reactionsCommunesID = new HashMap<String, String>();


		//preparation des sommets
		Map<String, DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>> sommet2Graph = new HashMap<String, DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>>();
		Map<String, Set<String>> sommet2ReactionsOfGraph = new HashMap<String, Set<String>>();
		Integer i = 0;
		Set<String> removedReactions = new HashSet<String>();
		for(DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge> g : graphes)
		{
			String v = i.toString();
			sommet2Graph.put(v, g);
			Set<String> value =  new HashSet<String>();
			for (Couple<String, String> c : g.vertexSet())
			{
				value.add(c.getSecond());
			}
			sommet2ReactionsOfGraph.put(v, value);
			graphReactions.addVertex(v);
			for (Couple<String,String> cx : g.vertexSet())
			{
				String x = cx.getSecond();
				removedReactions.add(x);
				if (graphReactions.containsVertex(x))
				{
					Set<DefaultWeightedEdge> edges = graphReactions.incomingEdgesOf(x);
					for (DefaultWeightedEdge e : edges)
					{
						graphReactions.addEdge(graphReactions.getEdgeSource(e), v);
					}

					edges = graphReactions.outgoingEdgesOf(x);
					for (DefaultWeightedEdge e : edges)
					{
						graphReactions.addEdge(v, graphReactions.getEdgeTarget(e));
					}
				}
				else
				{
					System.err.println("Reaction inconnue : " + x);
				}
			}
			i++;
		}
		//System.out.println("nb sommets : " + graphReactions.vertexSet().size() + " nb arcs : " + graphReactions.edgeSet().size());		


		graphReactions.removeAllVertices(removedReactions);
		for (String v : sommet2Graph.keySet())
		{
			if (graphReactions.containsEdge(v, v))
			{
				graphReactions.removeEdge(v, v);
			}
		}

		Map<DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>, String> graph2Sommet = new HashMap<DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>, String>();
		for (Entry<String, DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>> entry : sommet2Graph.entrySet())
		{
			graph2Sommet.put(entry.getValue(), entry.getKey());
		}
		//ponderation 0 pour chaque arc entre modules partageant des reactions
		for (Entry<String, Set<DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>>> entry : reactionsCommunes.entrySet())
		{

			if (entry.getValue().size()>1)
			{
				for (DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge> g1 : entry.getValue())
				{
					String n1 = graph2Sommet.get(g1);
					for (DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge> g2 : entry.getValue())
					{
						String n2 = graph2Sommet.get(g2);
						//System.err.print(n1 + "->" + n2);
						if (graphReactions.containsEdge(n1, n2))
						{
							//System.err.print(" " + graphReactions.containsEdge(n1, n2));
							DefaultWeightedEdge e = graphReactions.getEdge(n1, n2);
							graphReactions.setEdgeWeight(e, 0);
						}
						//System.err.println();
					}
				}
			}
		}


		for (Entry<String, Set<DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge>>> entry : reactionsCommunes.entrySet())
		{
			if (entry.getValue().size()>1)
			{
				System.err.println(entry.getKey());
				Set<String> reactions = new TreeSet<String>();
				for (DefaultDirectedWeightedGraph<Couple<String, String>, DefaultWeightedEdge> g: entry.getValue())
				{
					reactions.add(graph2Sommet.get(g));
				}
				for (String r : reactions)
				{
					reactionsCommunesID.put(r, "\""+reactions.toString()+"\"");
				}
			}
		}
		System.err.println(reactionsCommunesID);


		System.out.println("nb sommets : " + graphReactions.vertexSet().size() + " nb arcs : " + graphReactions.edgeSet().size());
		System.out.println("reactions retirees : " + removedReactions.size() + " sommets ajoutes : " + graphes.size());
		//System.err.println(sommet2ReactionsOfGraph);
		// calcul des plus courts chemins inter-sous-graphes sur le metabolisme. 
		// creation d'un nouveau graphe ayant les sous-graphes en sommet et les liens entre ces sous-graphes dans le metabolisme (lien inter-sous-graphe)

		Map<DefaultWeightedEdge, Double> poids = new HashMap<DefaultWeightedEdge, Double>();
		DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> graphInterNSIP = new DefaultDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
		for (String src : sommet2ReactionsOfGraph.keySet())
		{
			if ( !graphInterNSIP.containsVertex(src))
			{
				//System.err.println("Ajout sommet : "+ src);
				graphInterNSIP.addVertex(src);
			}
			for (String dest : sommet2ReactionsOfGraph.keySet())
			{
				if (src != dest)
				{
					if ( !graphInterNSIP.containsVertex(dest))
					{
						//System.err.println("Ajout sommet : "+ dest);
						graphInterNSIP.addVertex(dest);
					}
					DijkstraShortestPath<String,DefaultWeightedEdge> dijkstra = new DijkstraShortestPath<String,DefaultWeightedEdge>(graphReactions, src, dest);
					GraphPath<String, DefaultWeightedEdge> acces = dijkstra.getPath();
					if (acces != null)
					{
						Set<String> reactCommunes = new HashSet<String>(sommet2ReactionsOfGraph.get(src));
						reactCommunes.retainAll(sommet2ReactionsOfGraph.get(dest));
						double weight = 0;
						String deb = acces.getStartVertex();
						String fin = acces.getEndVertex();
						//System.err.println("Etude : " + deb + "->" + fin + " : " + dijkstra.getPathLength());
						for (DefaultWeightedEdge e : acces.getEdgeList())
						{
							weight = weight + graphReactions.getEdgeWeight(e);
							fin = graphReactions.getEdgeTarget(e);
							if (sommet2ReactionsOfGraph.keySet().contains(graphReactions.getEdgeTarget(e)))
							{
								// eclatement du chemin
								if (! reactCommunes.isEmpty())
								{
									weight=0;
								}
								if (graphInterNSIP.containsEdge(deb, fin) && graphInterNSIP.getEdgeWeight(graphInterNSIP.getEdge(deb, fin)) != weight)
								{
									System.err.println("Arcs doubles : " + deb + "->" + fin + " : " + graphInterNSIP.getEdgeWeight(graphInterNSIP.getEdge(deb, fin)) + " vs " + weight);
									System.err.println("Ajout chemin : " + deb + "->" + fin + " : " +  weight);
								}
								if ( !graphInterNSIP.containsVertex(fin))
								{
									//System.err.println("Ajout sommet : "+ dest);
									graphInterNSIP.addVertex(fin);
								}
								//								if ( !graphInterNSIP.containsVertex(deb))
								//								{
								//									//System.err.println("Ajout sommet : "+ dest);
								//									graphInterNSIP.addVertex(deb);
								//								}
								//System.err.println("Ajout chemin : " + deb + "->" + fin + " : " +  weight);

								graphInterNSIP.addEdge(deb, fin);
								DefaultWeightedEdge edge = graphInterNSIP.getEdge(deb, fin);
								graphInterNSIP.setEdgeWeight(edge, weight);
								poids.put(edge, weight);

								weight = 0;
								deb = fin;
							}
						}

					}
				}
			}
		}

		// export au format dot (2 versions avec boites et sans boites).
		DOTColorWithFullSubgraphExporter<String, DefaultWeightedEdge,Couple<String, String>, DefaultWeightedEdge> outGraphInterNSIP = new DOTColorWithFullSubgraphExporter<String, DefaultWeightedEdge, Couple<String, String>, DefaultWeightedEdge>(
				new IntegerNameProvider<String>(),
				new StringNameProvider<String>(),
				new DOTWeightedEdgeNameProvider<DefaultWeightedEdge>(poids)
				);
		try {

			outGraphInterNSIP.export(new BufferedWriter(new FileWriter(pathTemplateGraph + "NSIP" + extTemplateGraph)), graphInterNSIP, sommet2Graph, 
					new DOTColorSubgraphExporter(new IntegerNameProvider<Couple<String,String>>(), new StringNameProvider<Couple<String,String>>(),null)
					);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}


	public static Couple<Collection<List<List<Couple<String, String>>>>, Map<List<Couple<String, String>>, Couple<Double,Integer>>> chargeFeuilles(String fileIn) throws IOException
	{		
		Collection<List<List<Couple<String, String>>>> result = new LinkedList<List<List<Couple<String, String>>>>();
		Map<List<Couple<String, String>>, Couple<Double,Integer>> map = new HashMap<List<Couple<String, String>>, Couple<Double,Integer>>();
		String ch;
		BufferedReader in;
		in = new BufferedReader (new FileReader(fileIn));
		String buffer = "";
		while ((ch = in.readLine()) != null)
		{
			if (ch.isEmpty()) //fini
			{
				Couple<List<List<Couple<String, String>>>, Map<List<Couple<String, String>>,Couple<Double, Integer>>> chemins = analyseBloc(buffer);
				if (!chemins.getFirst().isEmpty())
				{
					//TODO passage a k>=1
					result.add(chemins.getFirst());
					map.putAll(chemins.getSecond());
					chemins.getSecond().clear();
				}
				buffer = "";
			}
			else{
				buffer = buffer + "\n" + ch;
			}
		}
		in.close();
		return new Couple<Collection<List<List<Couple<String, String>>>>, Map<List<Couple<String, String>>, Couple<Double,Integer>>>(result, map);
	}


	private static Couple<List<List<Couple<String, String>>>, Map<List<Couple<String, String>>,Couple<Double, Integer>>> analyseBloc(String bloc) {
		Couple<List<List<Couple<String, String>>>, Map<List<Couple<String, String>>,Couple<Double, Integer>>> result = new Couple<List<List<Couple<String, String>>>, Map<List<Couple<String, String>>,Couple<Double, Integer>>>(new ArrayList<List<Couple<String, String>>>(), new HashMap<List<Couple<String, String>>,Couple<Double, Integer>>());
		Matcher m;
		String recoReaction = "(?:" +"[^ \t,\\]\\[)(]+" + ")";
		String beginBloc = "(?:(" + recoReaction + ")->(" + recoReaction + "))";
		//String sommetChemin = "(?:"+ "(?:" + "\\([+-]?([^:]+)[^,]*,(" + recoReaction  + ")\\))" + ")"; //gloutonnerie limit�e
		String poidEtLongueurChemin = "^([^\t]+)\t([^\t]+)\t[^\t]+$";
		String sommetChemin = "(?:"+ "(?:" + "\\(([^:]+):(" + recoReaction  + ")\\))" + ")"; //gloutonnerie limit�e

		Pattern recoBloc = Pattern.compile(beginBloc);
		Pattern recoSommetChemin = Pattern.compile(sommetChemin);
		Pattern recoPoidEtLongueurChemin = Pattern.compile(poidEtLongueurChemin);
		boolean estBloc = false;
		int cpt = 0;
		for (String s : bloc.split("\n"))
		{
			try
			{
				if (cpt == 0)
				{
					m = recoBloc.matcher(s);
					estBloc = estBloc || m.find();
				}
				else
				{
					m = recoPoidEtLongueurChemin.matcher(s);
					double w = Double.NaN;
					int l = -1;
					while(m.find())
					{
						w=Double.parseDouble(m.group(1));
						l=Integer.parseInt(m.group(2));
					}
					m = recoSommetChemin.matcher(s);
					LinkedList<Couple<String,String>> path = new LinkedList<Couple<String,String>>();
					while(m.find())
					{
						Couple<String, String> v = new Couple<String,String>(m.group(1), m.group(2));
						path.addLast(v);
					}
					if (!path.isEmpty())
					{
						result.getFirst().add(path);
						result.getSecond().put(path,new Couple<Double,Integer>(w, l));
					}
				}
			}
			catch (Exception e)
			{
				e.printStackTrace();
			}
			cpt++;
		}

		return result;
	}


	private static DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> toWeigthedGraph(DirectedGraph<String, DefaultEdge> graph)
	{
		DefaultDirectedWeightedGraph<String, DefaultWeightedEdge> result = new DefaultDirectedWeightedGraph<String, DefaultWeightedEdge>(DefaultWeightedEdge.class);
		for (String s : graph.vertexSet())
		{
			result.addVertex(s);
		}
		for(DefaultEdge e : graph.edgeSet())
		{
			result.setEdgeWeight(result.addEdge(graph.getEdgeSource(e), graph.getEdgeTarget(e)),graph.getEdgeWeight(e));
		}
		return result;
	}

}
